package DataStructuresTest;

import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringJoiner;

public class Solution {
    /**
     * 查找出出现次数最多的元素
     */
    public void test(String str)
    {
        int max_length = 0;
        String max_str = "";
        while (str.length() > 0)
        {
            System.out.println(str);
            int length = str.length();
            //取第一个字符
            String first = str.substring(0, 1);
            //去掉str里面所有的first字符
            str = str.replaceAll(first, "");
            //原来的字符长度-去掉后的字符长度 =去掉的所有字符的长度
            if (max_length < length - str.length())
            {
                max_length = length - str.length();
                max_str = first;
            }
        }
        System.out.println("");
        System.out.println("出现次数最多的字符:" + max_str + ";出现的次数:" + max_length);
    }


    /**
     * turnToPostfix(转为后缀表达式)
     * 思路:  变量准备：定义一个栈，stack用于存储符号，定义一个String变量result，用于存储结果
     *          1.遍历字符串 
     *          2.判断是+，-，*，/，(，)。还是数字
     *              2.1当读到操作符时，如果栈是空栈，则直接入栈，
     *                  2.2.1如果是左括号则入栈，如果是右括号则不停从栈弹出，并写入result，直到弹出左括号为止
     *                  2.2.2否则（也就是+，-，*，/的情况）比较栈顶操作符号temp和当前遍历到的操作符号strings[i]之间的优先级，
     *                       若temp<strings[i]或者temp是左括号"("则将strings[i]入栈（因为优先级小的需要后算，优先级大的需要先算），
     *                       否则将strings[i]写入result
     *              2.3当读到的是数字时，直接将数字写入result
     *          3.遍历完成后将栈中的符号全部写入result中
     */
    public String turnToPostfix(String infixFormula){
        String result = null;
        String[] strings = infixFormula.split(" ");
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < strings.length; i++) {
            if (isOperator(strings[i])){//当读到操作符时
                //先存到栈中

                    //栈空入栈
                    if (stack.isEmpty()){
                        stack.push(strings[i]);
                        continue;
                    }
                    String temp = null;
//                    if (strings[i].equals("("))stack.push(strings[i]);
                    if (strings[i].equals(")")){//当遇到")"，将元素弹出直到遇到一个"("
                        while (true){
                            temp = stack.pop();
                            if (temp.equals("("))break;
                            result += temp+" ";
                        }
                    }else {
                        while (true){
                            if (stack.isEmpty()){
                                stack.push(strings[i]);break;
                            }
                         temp = stack.peek();
                         if (isLower(temp,strings[i]) || temp.equals("(")){stack.push(strings[i]);break;}
                         result += stack.pop() +" ";
                        }
                    }

            }else {//当读到操作数时
                if (result == null)result = strings[i]+" ";
                else result+=strings[i]+" ";//将操作数放入output的string中
            }
        }
        while (true){//最后读到输入的末尾，我们将栈元素弹出，直到为空，同时写入到result中
            if (stack.isEmpty())break;
            String temp = stack.pop();
            result += temp + " ";
        }
        return result;
    }
    //判断优先级
    public boolean isLower (String string0,String string1){
        HashMap<String,Integer> hashMap = new HashMap<String,Integer>();
        hashMap.put("+",1);hashMap.put("-",1);hashMap.put("*",2);hashMap.put("/",2);hashMap.put("(",3);
        int a = hashMap.get(string0);
        int b = hashMap.get(string1);
        return a < b;
    }

    /**
     * postfixCalculator
     */
    public int postfixCalculator(String formula){
        int result = 0;
        //将formula切分
        String[] strings = formula.split(" ");
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < strings.length; i++) {
            if (isOperator(strings[i])){
                int num0 = stack.pop();
                int num1 = stack.pop();
                switch (strings[i]){
                    case "+":stack.push(num0+num1);continue;
                    case "-":stack.push(num0-num1);continue;
                    case "*":stack.push(num0*num1);continue;
                    case "/":stack.push(num0/num1);continue;
                    default:
                        System.out.println("error");continue;
                }
            }else {
                stack.push(Integer.parseInt(strings[i]));
            }
        }
        result = stack.pop();
        return result;
    }
    public boolean isOperator(String string){
        return string.equals("+") || string.equals("*") || string.equals("-") || string.equals("/") || string.equals("(") || string.equals(")");
    }

    /**
     * 平衡符号
     * 使用栈来判断括号是否对称
     */
    public boolean isBalanceSymbol(String string,char symbol0,char symbol1){
        char[] chars = string.toCharArray();
        //创建栈
        Stack stack = new Stack();
        //读入字符直到结尾
        for (int i = 0; i < chars.length; i++) {
            //如果字符是一个开放符号就将字符推入栈中
            if (chars[i] == symbol0)
                stack.push(chars[i]);
            else if (chars[i] == symbol1){//如果是一个封闭符号
                if (stack.empty())return false;
                char c = (char) stack.pop();
                if (c != symbol0)return false;
            }
        }
        if (stack.empty())return true;
        else return false;
    }

    /**
     * 扩大数组
     * array为原数组，newArray为扩大后的数组
     */
    public int[] expandArray(int[] array){
        int[] newArray = new int[array.length*2];
        for (int i = 0; i < array.length; i++) {
            newArray[i] = array[i];
        }
        return newArray;
    }

    /**
     * 幂运算
     * 求出x的n次方，最坏时间复杂度为2logN
     */
    public long pow(long x,int n){
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        if (n%2 == 0)
            return pow(x*x,n/2);
        else return pow(x*x,n/2)*x;
    }

    /**
     * 欧几里得算法（gcd）辗转相除法
     * 算法连续计算余数直到余数是0为止，最后的非零余数就是最大整数
     */
    public long gcd(long m,long n){
        if(n>m){
            long temp = m;
            m = n;
            n = temp;
        }
        while (n != 0){
            long rem = m % n;
            m = n;
            n = rem;
        }
        return m;
    }

    /**
     * 折半查找
     * 给定一个整数x和一串已经排好的整数a1,a2,a3,a4....an，求下标i使得ai = x,如果不存在则返回-1.
     */
    public int binarySearch(int[] array,int x){
        int low = 0,height = array.length-1;
        while (low < height){
            int mid = (low+height)/2;
            if (array[mid] == x){
                return mid;//找到
            }else if (array[mid] < x){
                low = mid+1;
            }else {
                height = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 最大子序列
     * 一串序列a1,a2,a3,a4,a5...an.求a0-ai的和的最大值
     * 递归解决
     */
    public int maxSumRec(int[] a,int left,int right){
        if (left == right){
            if (a[left] > 0){
                return a[left];
            }else
                return 0;
        }
        int center = (left+right)/2;
        int maxLeftSum  = maxSumRec(a,left,center);
        int maxRightSum = maxSumRec(a,center+1,right);

        int maxLeftBorderSum = 0,leftBorderSum = 0;
        for (int i = center; i >= left; i--) {
            leftBorderSum += a[i];
            if (leftBorderSum > maxLeftBorderSum){
                maxLeftBorderSum = leftBorderSum;
            }
        }

        int maxRightBorderSum = 0,rightBorderSum = 0;
        for (int i = center+1; i < right; i++) {
            rightBorderSum += a[i];
            if (rightBorderSum > maxRightBorderSum){
                maxRightBorderSum = rightBorderSum;
            }
        }
        return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
    }

    /**
     * 最大子序列
     * 一串序列a1,a2,a3,a4,a5...an.求a0-ai的和的最大值
     * O（n）
     */
    public int maxSum(int[] array){
        int maxSum = 0,sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
            if (maxSum < sum){
                maxSum = sum;
            }else if (sum < 0){
                maxSum = 0;
            }
        }
        return maxSum;
    }

    /**
     * 求最大值
     */
    public int max3(int a,int b,int c){
        int max;
        if (a>b)max = a;
        else max = b;
        if (max < c)max = c;
        return max;
    }

    /**
     * 先指定数组长度length，向一串长度为length的数组中输入数据
     */
    public void enterDataIntoArray(){
        System.out.println("请输入数组长度：");
        Scanner scanner = new Scanner(System.in);
        int length  = scanner.nextInt();
        System.out.println("请输入数组");
        int array[] = new int[length];
        for (int i = 0; i < length; i++) {
            array[i] = scanner.nextInt();
        }
    }
    /**
     * 数组翻转
     */
    public void reverse(int[] array,int start,int end){
        for (int i = 0; i < (end-start)/2; i++) {
            int temp = array[start+i];
            array[start+i] = array[end-i];
            array[end-i] = temp;
        }
    }

    /**
     * 打印数组
     */
    public void printArray(int[] array){
        int n = array.length;
        for (int i = 0; i < n; i++) {
            System.out.print(array[i]);
            if (i<n-1) System.out.print(" ");
        }
    }

    /**
     * 假设将n个整数放到一个数组array中，将array中的数组循环左移P个位置
     * 思路：可将该问题视为ab(a代表0到p个元素，b代表p+1到n个元素)转化为ba，
     * 1.先把a倒置
     * 2.再将b倒置，得到a的-1次方*b的-1次方
     * 3.再将整体倒置，得到ba
     */
    public void page_18_10(int p,int[] array){
        int min = array[0];
        //1.先把a倒置
        reverse(array,0,p-1);
        reverse(array,p,array.length-1);
        reverse(array,0,array.length-1);
        printArray(array);
    }

    /**
     *数组右移
     */
    public int[] rightShiftArray(int[] array,int p){
        int[] array0 = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            array0[(i+p)%array.length] = array[i];
        }
        array = array0;
        printArray(array);
        return array;
    }

    /**
     * 选择数
     * 输入一串数，输入一个数字k
     * 输出这串数字中的第k大的数
     */


    /**
     * 归并排序
     * 速度仅次于快速排序，安全的排序算法
     * 一般用于对总体无序，但是各子项相对有序的数列。
     */
    public void mergeSort(int[] array,int start,int end){
        int[] result = new int[end];
        merge_sort_recursive(array, result, start, end - 1);
    }
    public void mergeSort(int[] array){
            int len = array.length;
            int[] result = new int[len];
            merge_sort_recursive(array, result, 0, len - 1);
    }
    private void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
        if (start >= end)
            return;
        int len = end - start, mid = (len >> 1) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        merge_sort_recursive(arr, result, start1, end1);
        merge_sort_recursive(arr, result, start2, end2);
        int k = start;
        while (start1 <= end1 && start2 <= end2)
            result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
        while (start1 <= end1)
            result[k++] = arr[start1++];
        while (start2 <= end2)
            result[k++] = arr[start2++];
        for (k = start; k <= end; k++)
            arr[k] = result[k];
    }
}
